﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm
{
    class ShortestPath
    {
        public ShortestPath()
        {
            int testCase = Int32.Parse(TestConsole.ReadLine());
            while (testCase-- > 0)
            {
                int cityCount = Int32.Parse(TestConsole.ReadLine());
                List<City> cityList = new List<City>();
                cityList.Add(new City(0, string.Empty));
                Dictionary<string, int> nameIndex = new Dictionary<string, int>();
                for (int i = 1; i <= cityCount; i++)
                {
                    string cityName = TestConsole.ReadLine().Trim();
                    City city = new City(i, cityName);
                    nameIndex.Add(cityName, i); //이름을 index로 변환하기 위해
                    int neighbourCount = Int32.Parse(TestConsole.ReadLine());
                    for (int j = 0; j < neighbourCount; j++)
                    {
                        string[] input = TestConsole.ReadLine().Split(' ');
                        city.AddNeighbour(Int32.Parse(input[0]), Int32.Parse(input[1]));
                    }
                    cityList.Add(city);
                }
                int resultCount = Int32.Parse(TestConsole.ReadLine());
                int[,] costBoard = new int[cityCount + 1, cityCount + 1]; 
                for (int i = 0; i < resultCount; i++)
                {
                    string[] input = TestConsole.ReadLine().Split(' ');
                    int startIndex = nameIndex[input[0].Trim()];
                    int endIndex = nameIndex[input[1].Trim()];
                    if (costBoard[startIndex, endIndex] > 0)
                    {
                        Console.WriteLine(costBoard[startIndex, endIndex]);
                        continue;
                    }
                    int[] costArray = new int[cityCount + 1];
                    for (int j = 0; j < costArray.Length; j++)
                    {
                        costArray[j] = -1;
                    }
                    costArray[startIndex] = 0;
                    Search(cityList, costArray, startIndex, endIndex);
                    Console.WriteLine(costArray[endIndex]);
                    for (int j = 1; j <= cityCount; j++)
                    {
                        costBoard[i, j] = costArray[j];
                        costBoard[j, i] = costArray[j];
                    }
                }
                TestConsole.ReadLine();
            }
        }
        private void Search(List<City> cityList, int[] costArray, int start, int end)
        {
            City now = cityList[start];
            for (int i = 0; i < now.neighbours.Count; i++)
            {
                City neighbour = cityList[now.neighbours[i][0]];
                int newCost = costArray[now.index] + now.neighbours[i][1];
                if (costArray[neighbour.index] == -1 || costArray[neighbour.index] > newCost)
                {
                    costArray[neighbour.index] = newCost;
                    Search(cityList, costArray, neighbour.index, end);
                }
            }
        }
    }
    class City
    {
        public int index { get; set; }
        public string name { get; set; }
        public List<int[]> neighbours = new List<int[]>();
        public City(int index, string name)
        {
            this.index = index;
            this.name = name;
        }
        public void AddNeighbour(int index, int cost)
        {
            neighbours.Add(new int[] { index, cost });
        }

    }
}
